Kryptologie und Komplexität

Beschreibung:
Behandelt werden sollen folgende Ziele und Methoden der Kryptologie: Vertraulichkeit, Authentifikation, elektronische Unterschriften, simultaner Austausch, öffentliche Schlüssel, RSA, Zahlentheorie, Primzahltests, Pseudozufallsgeneratoren, Einwegfunktionen, Falltürfunktionen, elektronisches Geld [3], Zeroknowledge Beweissysteme, interaktive Beweissysteme [2], Kartenspiel übers Netz, Münzwurf per Telefon, Bestimmung des Älteren ohne Altersangabe, das Teilen von Geheimnissen, Verhinderung des Misbrauchs von Kryptosystemen [4]. Ferner werden wir Zusammenhänge zu den Komplexitätsklassen NP, RP, UP und BPP, zu Propositionallogik und zu formalsprachlichen Problemen [1] betrachten.

Voraussetzungen:
Grundstudium Informatik oder Komplexitätstheorie I

Bemerkungen:

Literatur:

1. M. Andrasiu, J. Dassow, A. Salomaa, G. Paun. Language-theoretic problems arising from Richelieu cryptosystems. Theoretical Computer Science 116, 1993.
2. Lazlo Babai. E-mail and the unexpected power of interaction. Proceedings of the 5-th Structure, 1990.
3. D. Chaum, A. Fiat, M. Naor. Untracable Electronic Cash. Proceedings of the CRYPTO88, 319­327.
4. Yvo Desmedt. Abuses in Cryptogrphy and How to Fight Them. Proceedings of the CRYPTO88, 374­389.
5. Ronald L. Rivest. Cryptographie. in L. van Leeuwen: Handbook of Theoretical Computer Science Volume A, The MIT Press/Elsevier, 1990.
6. Douglas R. Stinson. Cryptography - Theory and Practice. CRC Press, 1990.

Zurück zur Übersicht